﻿#include <iostream>
#include <unordered_set>

using namespace std;

static const int M[] = {
    1, 1,
    1, 0,
};

static unordered_set<int> fibonacciNumbers;

static void calcFibonacciNumbers(int n)
{
    fibonacciNumbers.clear();
    int* arr = (int*)malloc(n * sizeof(int));
    arr[0] = 1;
    arr[1] = 2;
    fibonacciNumbers.insert(arr[0]);
    fibonacciNumbers.insert(arr[1]);
    for (int i = 3; i <= n; i++)
    {
        arr[i - 1] = arr[i - 2] + arr[i - 3];
        fibonacciNumbers.insert(arr[i - 1]);
    }
}

static int howManyRemovedAtLeast(int n)
{
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (fibonacciNumbers.find(i) == fibonacciNumbers.end())
            ++count;
    }

    return count;
}

// 在迷迷糊糊的大草原上，小红捡到了n根木棍，第i根木棍的长度是i，小红现在很开心。想选出其中的三根木棍组成美丽的三角形。
// 但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍都不能组成三角形。
//
// 请问，小明最少去掉多少根木棍呢？
// 给定N，返回至少去掉多少根。
//
// 思路：
// 这道题目也和裴波那契数列有关，裴波那契数列表示的长度刚好任意三个无法搭成三角形.
// 用极限法想象一下，假设三角形的两条边长分别为1和2，则第三条边的长度至少比1大一点点，比3小一点点，
// 才能构成三角形。
// 所以，如果只保留能组成符合裴波那契数列长度的木棍，是无法任意三根组成三角形的。
int main_UseSticksToMakeTriangle()
{
    calcFibonacciNumbers(40);
    for (int n = 1; n <= 100; n++)
    {
        printf("[%d]=%d\n", n, howManyRemovedAtLeast(n));
    }
    return 0;
}